package tree;


import java.util.*;

/**
 * 给定一个二叉搜索树和一个目标结果，
 * 如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true
 * @author le
 */
public class TwoSumInBinarySearchTree
{
    public static void main(String[] args)
    {
        int[] nums = {2,7,11,15};
        int[] sum = twoSum(nums, 9);
        System.out.println(sum[0]+"  ---  "+sum[1]);
    }

    public static int[] twoSum(int[] nums, int target) {
        int[] num = new int[2];
        int low = 0;
        int high = nums.length-1;
        while(low < high){
            if (nums[low] + nums[high] > target){
                high--;
            }else if (nums[low] + nums[high] < target){
                low++;
            }else{
                num[0] = low;
                num[1] = high;
                return num;
            }
        }
        return num;
    }

    public boolean findTarget(TreeNode root, int k) {
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null){
            queue.offer(root);
        }
        List<Integer> res = new ArrayList<>();
        while(!queue.isEmpty()){
            int size = queue.size();
            while (size-- > 0){
                TreeNode tmp = queue.poll();
                res.add(tmp.val);
                if (tmp.left != null){
                    queue.offer(tmp.left);
                }
                if (tmp.right != null){
                    queue.offer(tmp.right);
                }
            }
        }
        int[] nums = new int[res.size()];
        int index = 0;
        for (int s : res){
            nums[index] = s;
            index++;
        }
        Arrays.sort(nums);
        int low = 0;
        int high = nums.length-1;
        while(low < high){
            if (nums[high] + nums[low] > k){
                high--;
            }else if (nums[high] + nums[low] < k){
                low++;
            }else{
                return true;
            }
        }


        return false;
    }
}
